package com.sicheng.蓝桥.练习题.dp.状态压缩;

import java.util.ArrayList;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/7 17:24
 */
@SuppressWarnings("unused")
public class K等划分 {

    int[][] dp; // 已经分了i组，用了状态为j的， 能达到为1，不能达到为0
    ArrayList<Integer> states; // 存合法状态

    boolean canPartitionKSubsets(int[] nums, int k) {
        //集合类状态压缩
        int sum = 0, avg;
        int n = nums.length;
        for (int x : nums) sum += x;
        // 如果不能均分，直接返回false;
        if (sum % k != 0)
            return false;
        avg = sum / k;
        for (int i = 0; i < (1 << n); ++i) {
            int x = 0;
            for (int j = 0; j < n; ++j) {
                //i状态下已经选了j
                if (((i >> j) & 1) == 1)
                    x += nums[j];
            }
            // 如果当前选法可以满足这一组的和为avg，则为合法状态
            if (x == avg)
                states.add(i);
        }
        // 初始化状态
        for (int i = 0; i <= k; ++i)
            dp[i][0] = 1; // 前i组，都不选一定可以达到
        for (int i = 1; i <= k; ++i) {
            for (int j = 0; j < (1 << n); ++j) {
                //在前i-1组已选j的情况下,第i组再把state状态选了
                for (int state : states) {
                    if ((j & state) != 0)
                        continue; // 有物品被重复选取，continue;
                    dp[i][j | state] = dp[i - 1][j] | dp[i][j | state];
                }
            }
        }
        return dp[k][(1 << n) - 1] == 1;
    }
}

